package sort;

/**
 * @author lakersUp
 * @Classname
 * @Description  实现堆排序
 * @Date HeapSort 10:57
 * @Version 1.0
 */
public class HeapSort {
    public static void heapSort(int[] arr){
        if(arr==null || arr.length==0){
            return;
        }
        int len=arr.length;
        //构建大顶堆
        buildMaxHeap(arr,len);
        //交换堆顶和当前末尾元素,重置大顶堆
        for(int i=len-1;i>=0;i--){
            swap(arr,0,i);
            //交换之后末尾元素就有序了,以后不用调整了
            len--;
            heapify(arr,0,len);
        }

    }

    private static void buildMaxHeap(int[] arr, int len) {
        // 从下往上遍历
        for(int i=(len/2)-1;i>=0;i--){
            heapify(arr,i,len);
        }
    }

    private static void heapify(int[] arr, int i, int len) {
        int left=2*i-1;
        int right=2*i+1;
        int largestIndex=i;
        if(left<len && arr[left]>arr[i]){
            largestIndex=left;
        }
        if(right<len && arr[right]>arr[i]){
            largestIndex=right;
        }
        if(largestIndex!=i) {
            swap(arr, largestIndex, i);
            //交换之后子节点的值变了,继续调整
            heapify(arr,largestIndex,len);
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp=arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;
    }
}
